package com.github.com.tools;

import java.math.BigDecimal;
import java.util.Arrays;

/**
 * 排列组合
 */
public class CombinationUtil {
	
	public static String result = "";
	public static String amt = "0";

	public static void combinationSelect(String[] dataList, int n) {
		System.out.println(String.format("C(%d, %d) = %d", dataList.length, n, combination(dataList.length, n)));
		combinationSelect(dataList, 0, new String[n], 0);
	}

	private static void combinationSelect(String[] dataList, int dataIndex, String[] resultList, int resultIndex) {
		if (null == result || "".equals(result)) {
			int resultLen = resultList.length;
			int resultCount = resultIndex + 1;
			if (resultCount > resultLen) {
				String sum = "0";
				for (int i = 0; i < resultList.length; i++) {
					sum = (new BigDecimal(sum).add(new BigDecimal(resultList[i]))).toString();
				}
				if (new BigDecimal(amt).compareTo(new BigDecimal(sum)) == 0) {
					result = Arrays.asList(resultList) + "=" + sum;
					System.out.println(Arrays.asList(resultList) + "=" + sum);
				}
				return;
			}
			// 递归选择下一个
			for (int i = dataIndex; i < dataList.length + resultCount - resultLen; i++) {
				resultList[resultIndex] = dataList[i];
				combinationSelect(dataList, i + 1, resultList, resultIndex + 1);
			}
		}
	}

	/**
	 * 计算阶乘数，即n! = n * (n-1) * ... * 2 * 1
	 * @param n
	 * @return
	 */
	public static long factorial(int n) {
		return (n > 1) ? n * factorial(n - 1) : 1;
	}

	/**
	 * 计算排列数，即A(n, m) = n!/(n-m)!
	 * @param n
	 * @param m
	 * @return
	 */
	public static long arrangement(int n, int m) {
		return (n >= m) ? factorial(n) / factorial(n - m) : 0;
	}

	/**
	 * 计算组合数，即C(n, m) = n!/((n-m)! * m!)
	 * @param n
	 * @param m
	 * @return
	 */
	public static long combination(int n, int m) {
		return (n >= m) ? factorial(n) / factorial(n - m) / factorial(m) : 0;
	}

}
